package solution.string;

import java.util.HashMap;
import java.util.Map;

import junit.framework.Assert;
import lib.util.Mutable;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class MinCoverWindow {

	boolean findMinCover(String keywords, String paragraph,
			Mutable<Integer> start, Mutable<Integer> end) {
		start.setValue(-1);
		end.setValue(-1);

		char keys[] = keywords.toCharArray(); // the keywords
		char para[] = paragraph.toCharArray(); // the paragraph

		Map<Character, Integer> keyCount = new HashMap<Character, Integer>();
		for (char key : keys) {
			keyCount.put(key, 0);
		}

		int numMissingKey = keys.length, minLen = para.length + 1;
		for (int startPos = 0, endPos = 0; endPos < para.length; endPos++) {
			// move endPos to include all keywords
			if (keyCount.containsKey(para[endPos])) {
				int cnt = keyCount.get(para[endPos]);
				keyCount.put(para[endPos], cnt + 1);
				if (cnt == 0) {
					numMissingKey--; // find one missing keyword.
				}
			}
			if (numMissingKey > 0) {
				continue;
			}

			// move startPos to find a min cover window, which has all keywords
			// but cannot be shorter
			for (; numMissingKey == 0 && startPos <= endPos; startPos++) {
				if (!keyCount.containsKey(para[startPos])) {
					continue;
				}
				int cnt = keyCount.get(para[startPos]);
				keyCount.put(para[startPos], cnt - 1);
				if (cnt > 1) {
					continue;
				}
				// this keyword is the only one in the substring. Now, this
				// keyword will be missing by moving startPos.

				// so, [startPos..endPos] is a candidate for min cover window.
				numMissingKey++;
				if (endPos - startPos < minLen) {
					minLen = endPos - startPos;
					start.setValue(startPos);
					end.setValue(endPos);
				}
			}
		}
		return minLen < para.length;
	}

	@Test
	public void test() {
		String[][] data = new String[][] {
				//
				{ "abc", "-aabbcc", "abbc" }, //
				{ "abc", "a-ababcc", "abc" }, //
				{ "abc", "aa-bbacc", "bac" }, //
				{ "abc", "aab-bcac", "bca" }, //
				{ "abc", "aabb-cca-", "abb-c" }, //
				{ "abc", "bca-", "bca" }, //
		};

		Mutable<Integer> start = new Mutable<Integer>(), end = new Mutable<Integer>();
		for (String[] element : data) {
			Assert.assertTrue(findMinCover(element[0], element[1], start, end));
			Assert.assertEquals(element[2],
					element[1].substring(start.getValue(), end.getValue() + 1));
		}

		data = new String[][] {
				//
				{ "abc", "-bbcc-" }, //
				{ "abc", "-aabb-" }, //
				{ "abc", "" }, //
				{ "abc", "-" }, //
				{ "abc", "-a-" }, //
				{ "abc", "-aaa-" }, //
				{ "abc", "-bbb-" }, //
		};
		for (String[] element : data) {
			Assert.assertFalse(findMinCover(element[0], element[1], start, end));
		}
	}
}
